package leetcode.lcp.lcp20220924;

import java.awt.Point;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

//Solution3Test
public class Solution3 {

	int[] x = new int[] { 0, -1, 0, 1 };// +1 左转
	int[] y = new int[] { 1, 0, -1, 0 };// -1 右转
	char[][] arr;
	int m, n;
	Set<Point> ans;
	Map<Integer, Set<Point>> been;

	public int[][] ballGame(int num, String[] plate) {
		m = plate.length;
		n = plate[0].length();
		arr = new char[m][n];
		for (int i = 0; i < m; i++) {
			arr[i] = plate[i].toCharArray();
		}
		ans = new HashSet<>();
		been = new HashMap<>();
		for (int i = 1; i < m - 1; i++) {
			if (arr[i][0] == '.')
				this.ff(i, 0, num, 0, i, 0);//
			if (arr[i][n - 1] == '.')
				this.ff(i, n - 1, num, 2, i, n - 1);
		}
		for (int i = 1; i < n - 1; i++) {
			if (arr[0][i] == '.')
				this.ff(0, i, num, 3, 0, i);
			if (arr[m - 1][i] == '.')
				this.ff(m - 1, i, num, 1, m - 1, i);
		}
		int len = ans.size();
		int[][] ret = new int[len][2];
		int w = 0;
		for (Point p : ans) {
			ret[w][0] = p.x;
			ret[w][1] = p.y;
			w++;
		}
		return ret;
	}

	public int index(int i, int j) {
		return i * n + j;
	}

	private void ff(int i, int j, int num, int k, int si, int sj) {
		if (i < 0 || i == m || j < 0 || j == n) {
			return;
		}
		int index = this.index(i, j);
		if (been.containsKey(index) && been.get(index).contains(new Point(num, k))) {
			return;
		}
		Set<Point> set = been.getOrDefault(index, new HashSet<>());
		set.add(new Point(num, k));
		been.put(index, set);
		if (arr[i][j] == 'O') {
			ans.add(new Point(si, sj));
			return;
		}
		if (num == 0) {// 最后的位置
			return;
		}
		if (arr[i][j] == 'W') {
			k = (k + 1) % 4;
		} else if (arr[i][j] == 'E') {
			k = (k + 3) % 4;
		}
		int numnext = num - 1;
		int nexti = i + x[k], nextj = j + y[k];
		this.ff(nexti, nextj, numnext, k, si, sj);
	}

}
